package com.tucc.hello.leetcode.no401_800.no692;

import java.util.*;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] words = {"glarko","zlfiwwb","nsfspyox","pwqvwmlgri","qggx","qrkgmliewc","zskaqzwo","zskaqzwo","ijy","htpvnmozay","jqrlad","ccjel","qrkgmliewc","qkjzgws","fqizrrnmif","jqrlad","nbuorw","qrkgmliewc","htpvnmozay","nftk","glarko","hdemkfr","axyak","hdemkfr","nsfspyox","nsfspyox","qrkgmliewc","nftk","nftk","ccjel","qrkgmliewc","ocgjsu","ijy","glarko","nbuorw","nsfspyox","qkjzgws","qkjzgws","fqizrrnmif","pwqvwmlgri","nftk","qrkgmliewc","jqrlad","nftk","zskaqzwo","glarko","nsfspyox","zlfiwwb","hwlvqgkdbo","htpvnmozay","nsfspyox","zskaqzwo","htpvnmozay","zskaqzwo","nbuorw","qkjzgws","zlfiwwb","pwqvwmlgri","zskaqzwo","qengse","glarko","qkjzgws","pwqvwmlgri","fqizrrnmif","nbuorw","nftk","ijy","hdemkfr","nftk","qkjzgws","jqrlad","nftk","ccjel","qggx","ijy","qengse","nftk","htpvnmozay","qengse","eonrg","qengse","fqizrrnmif","hwlvqgkdbo","qengse","qengse","qggx","qkjzgws","qggx","pwqvwmlgri","htpvnmozay","qrkgmliewc","qengse","fqizrrnmif","qkjzgws","qengse","nftk","htpvnmozay","qggx","zlfiwwb","bwp","ocgjsu","qrkgmliewc","ccjel","hdemkfr","nsfspyox","hdemkfr","qggx","zlfiwwb","nsfspyox","ijy","qkjzgws","fqizrrnmif","qkjzgws","qrkgmliewc","glarko","hdemkfr","pwqvwmlgri"};
        int k = 14;
        //["nftk","qkjzgws","qrkgmliewc","nsfspyox","qengse","htpvnmozay","fqizrrnmif","glarko","hdemkfr","pwqvwmlgri","qggx","zskaqzwo","ijy","zlfiwwb"]
        List<String> result = solution.topKFrequent(words, k);
        result.forEach(System.out::println);
    }

    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            Integer count = map.get(word);
            if (count == null) {
                count = 1;
            } else {
                count++;
            }
            map.put(word, count);
        }
        PriorityQueue<Map.Entry<String, Integer>> queue = new PriorityQueue<>(this::comparing);
        for(Map.Entry<String, Integer> entry : map.entrySet()){
            if(queue.size() < k){
                queue.offer(entry);
            }
            else{
                if(comparing(queue.peek(), entry) < 0){
                    queue.poll();
                    queue.offer(entry);
                }
            }
        }
        ArrayList<String> list = new ArrayList<>(queue.size());
        list.ensureCapacity(queue.size());
        for(int i = 0;i < k;i ++) {
            list.add(queue.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }


    public int comparing(Object a, Object b){
        Map.Entry<String, Integer> o1 = (Map.Entry<String, Integer>) a;
        Map.Entry<String, Integer> o2 = (Map.Entry<String, Integer>) b;
        int result = o1.getValue().compareTo(o2.getValue());
        return result != 0 ? result : -o1.getKey().compareTo(o2.getKey());
    }
}
